//060. 素数对集合
//        素数 3, 7, 109, 673 很有意思，从中任取两个素数以任意顺序拼接起来形成的仍然是素数。
//        例如，取出 7 和 109，7109 和 1097 都是素数。这四个素数的和是 792，是具有这样性质的
//        四个素数的最小的和。求满足以上性质的五个素数的最小的和。
//        答案：26033 （五个素数是：13, 5197, 5701, 6733, 8389）

import java.util.Arrays;

// 从小到大判断当前数能不能分解成五个质数相加，在判断它任意拼接是否为素数
public class Week060 {
    /*
     *@ prime[i] :第i+1个素数
     *@ mv[i]    :i的最小质因子
     *@ 质数的最小质因子为它本身
     *@ 请不要更改传入的数组的值（即全为0）
     */
    // 欧拉筛1~n的素数
    public static int getPrime(int[] prime, int[] mv, final int n) {
        int tot = 0;
        for (int i = 2; i <= n; ++i) {
            if (mv[i] == 0) {
                prime[tot++] = i;
                mv[i] = i;
            }
            for (int j = 0; j < tot && i * prime[j] <= n; ++j) {
                mv[i * prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
        return tot;
    }


    static final int MAX_SIZE = (int) 1e5;
    static final int NUMBER = 4;
    static int[] primes, mv;
    static int[] num;
    //当前prime是否选择
    static int cnt;

    public static boolean isPrime(final int n) {
        if (n <= MAX_SIZE) return mv[n] == n;
//        if (n <= 3) return n > 1;
        if (n % 6 != 1 && n % 6 != 5) return false;
        for (int i = 5, sq = (int) Math.sqrt(n); i <= sq; i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }

    //将y拼接到x后面
    static int join(int x, final int y) {
        int t = y;
        while (t != 0) {
            t /= 10;
            x *= 10;
        }
        return x + y;
    }

    //检查所选元素任意拼接后是否为素数
    static boolean check() {
        for (int i = 0; i < NUMBER; ++i) {
            for (int j = i + 1; j < NUMBER; ++j) {
                if (!isPrime(join(num[i], num[j])) || !isPrime(join(num[j], num[i]))) {
                    return false;
                }
            }
        }
        return true;
    }

    //二分查找找到第一个大于等于val的数的下标
    //左闭右开
    static int lowerbound(int l, int r, final int val) {
        while (l < r) {
            int mid = l + r >> 1;
            if (primes[mid] >= val) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    static boolean dfs(final int n, final int res, final int limit) {
        //当差一个的时候这个数已经是确定的了
//        if (n == 1) {
//            System.out.println(Arrays.toString(num));
//            //如果不是素数
//            if (!isPrime(res)) return false;
//            num[0] = res;
//            return check();
//        }
        if (n == 0) {
//            控制台输出太慢，建议输出到文件中查看
//            System.out.println(Arrays.toString(num));
            return check();
        }
        for (int i = 0; i < limit; ++i) {
            num[n - 1] = primes[i];
            //如果已经找到答案，直接return
            if (dfs(n - 1, res - primes[i], lowerbound(0, limit, Math.min(num[n - 1], res - primes[i])))) return true;
        }
        return false;
    }


    static boolean solve(final int n, final int sum) {
        return dfs(n, sum, lowerbound(0, cnt, sum));
    }

    static void run() {
        primes = new int[MAX_SIZE >> 1];
        mv = new int[MAX_SIZE + 1];
        num = new int[NUMBER];
        cnt = getPrime(primes, mv, MAX_SIZE);
        int cur = 0;
        for (int i = 0; i < NUMBER; ++i) cur += primes[i];
        while (!solve(NUMBER, cur)) ++cur;
        System.out.println(cur - 1);
        System.out.println(Arrays.toString(num));
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        run();
        System.out.println("\n程序运行时间：" + (System.currentTimeMillis() - startTime) + "ms.");
    }
}